package leetcode.level2;

import static utils.Tool.pt;

/**
 * 48. 旋转图像
 * 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-image
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

更进一步：降低内存使用，，比如，使用 栈

 * @author ben
 * @date 2021-10-27 10:20:49 CST
 */
public class Solution48 {

	/*
	 * n x n 矩阵（方阵）
	 */
    public static void rotate(int[][] matrix) {
    	rotateRight90(matrix);
    }
    
    /**
     * 右转90°
     * @author ben
     * @date 2021-10-27 10:33:50 CST
     * @param matrix
     */
    public static void rotateRight90(int[][] matrix) {
    	int n = matrix.length;
    	
    	// 内存占用比较高
    	int[] fullel = new int[n * n];
    	int idx = 0;
    	for (int i=0; i<n; i++) {
    		for (int j=0; j<n; j++) {
    			fullel[idx++] = matrix[i][j];
    		}
    	}

    	for (int i=0; i<n; i++) {
    		for (int j=0; j<n; j++) {
    			// i,j = (n - j - 1),i
    			int r = n - j -1;
    			int elidx = r * n + i;
    			matrix[i][j] = fullel[elidx];
    		}
    	}
    }
    
	public static void main(String[] args) {
		int[][] arr1 = {{1,2,3},{4,5,6},{7,8,9}};
		
		pt("arr1 转换前：");
		printMatrix(arr1);
		rotate(arr1);
		pt("arr1 转换后：");
		printMatrix(arr1);
		
		pt();
		
		int[][] arr2 = {{5,1,9,11},{2,4,8,10},{13,3,6,7},{15,14,12,16}};
		pt("arr2 转换前：");
		printMatrix(arr2);
		rotate(arr2);
		pt("arr2 转换后：");
		printMatrix(arr2);
		
	}
	
	public static void printMatrix(int[][] matrix) {
		final int n = matrix.length;
    	for (int i=0; i<n; i++) {
    		for (int j=0; j<n; j++) {
    			System.out.print(matrix[i][j] + " ");
    		}
    		pt();
    	}
	}
	
}
